package pro.softzhang.algo.lc700;

import pro.softzhang.algo.flag.knowledge.KGraph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 */
@KGraph
public class LC785_IsGraphBiparties {
    public static void main(String[] args) {

    }

    /**
     * 
     */
    static
    class Solution {
        public boolean isBipartite(int[][] graph) {
            int size = graph.length;
            int[] colors = new int[size];
            Arrays.fill(colors, -1);
            for (int i = 0; i < size; i++) {
                if(colors[i] == -1) {
                    if(!setColor(graph, colors, i, 0)) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean setColor(int[][] graph, int[] colors, int i, int color) {
            Queue<Integer> q = new LinkedList<>();
            q.add(i);
            colors[i] = color;
            while (!q.isEmpty()) {
                int v = q.remove();
                for (int neighbor : graph[v]) {
                    if(colors[neighbor] >= 0) {
                        if(colors[neighbor] == colors[v]) {
                            return false;
                        }
                    } else {
                        q.add(neighbor);
                        colors[neighbor] = 1 - colors[v];
                    }
                }
            }
            return true;
        }
    }
}
